package com.zzz.sort.quick;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author zizan
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] array = new int[]{5, 1, 7, 4, 2, 7, 3, 1, 9};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    /*
    传说中的快排，记了n次，遗忘了n次
    同理，需要递归实现
    原理：拿到数组第一个元素，然后从后面查找到比第一个数小的，
    左边都比它小，右边都比它大
    然后递归对左边排序 | 对右边排序
    思考: 是比需先划分好然后才能对左边和右边进行排序
     */
    public static void sort(int[] array) {
        //必须使用新的方法，因为递归的参数要包含 开始位置和结束位置
        sort(array, 0, array.length - 1);
    }

    public static void sort(int[] array, int low, int high) {
        // 剩一个元素了 那直接返回，没办法给一个元素进行拆分了啊
        if (low >= high) {
            return;
        }
        // 将数组按头元素分开
        int midIndex = partition(array, low, high);
        sort(array, low, midIndex - 1);
        sort(array, midIndex + 1, high);
    }

    // 将数组划分成两部分 左边是小于   右边是大于等于
    // 这个算法是教科书 数据结构里面的，不跟算法第4版那样技巧性强，
    // 而是在进行遍历查找的时候留一个 等候位置，候选位置在左边的时候，将遍历右边找到比temp小的数填进去
    // 候选位置被比temp小的数填进去了，自然原来j的位置就变成候选位置
    // 那将从左边i的位置开始i++ 遍历，找到到比temp大的数填进去，，
    // 直到i==j  i的位置就是temp的位置了
    // i==j的情况下，遍历完了，左边小于 temp，右边>=temp
    public static int partition(int[] array, int low, int high) {
        int temp = array[low];
        int i = low, j = high;

        while (i < j) {

            while (i < j && array[j] >= temp)
                j--;
            if (i < j) {
                // 把比temp小的数 转到 i的位置
                array[i] = array[j];
            }

            // 接着 如果i 依然小于j的话，从i开始遍历，找到比tem大的数
            while (i < j && array[i] < temp)
                i++;
            //如果找到了比tem大，并且i<j 那么将i的数换到j的位置
            if (i < j) {
                array[j] = array[i];
            }
            // 那么i的位置就作为下一个换的位置，后面就是遍历j-- 如果知道i=j那么，i的位置就是最终位置，放入temp
        }
        array[i] = temp;
        return i;
    }

}
